package recursive.KthGrammar;
/**
 * @Date 2020/03/30
 * @author 王光浩
 * @Thinking 使用递归实现
 * @Analysis 时间复杂度O（2^n），空间复杂度O（2^n）,不能ac，超出内存限制
 */
public class MyMethodTwo {
	public int kthGrammar(int N, int K) {
		return recursive(N).charAt(K-1);
	}
	private String recursive(int N) {
		if(N==1)return String.valueOf(0);
		String tem=recursive(N-1);
		StringBuilder ret=new StringBuilder(tem);
		for(int i=0;i<tem.length();i++) {
			if(tem.charAt(i)=='0')ret.append(1);
			else ret.append(0);
		}
		return ret.toString();
	}
}
